<!DOCTYPE html>
<meta charset="utf-8">
<script src="//code.jquery.com/jquery-1.11.3.min.js"></script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script>
  MathJax.Hub.Config({
                      tex2jax: {inlineMath: [['$', '$'], ['\\(','\\)']]},
                      TeX: { equationNumbers: {autoNumber: "AMS"} },
                      "HTML-CSS": { showMathMenu: false,
                                    scale: 90 }

                     });
</script>
<link rel="stylesheet" href="http://yui.yahooapis.com/pure/0.4.2/pure-min.css">
<style>
@import url(http://fonts.googleapis.com/css?family=PT+Serif|PT+Serif:b|PT+Serif:i|PT+Sans|PT+Sans:b);
@import url(http://fonts.googleapis.com/css?family=Lato);
html {
   min-width: 1040px;
}

body {
   background: #fcfcfa;
   color: #333;
   font-family: "PT Serif", serif;
   /*margin: 0 1em 4em auto;*/
   position: relative;
   width: 960px;
   left: 13em;
}

h1, h2, h3, h4 { font-family: "Lato", "PT Serif", serif; color: #000; text-rendering: optimizeLegibility; }

h1 {
  font-size: 64px;
  line-height: 73px;
  font-weight: 900;
  margin-top: 0.67em;
  margin-right: 0;
  margin-bottom: 0;
  margin-left: 0;
}

h2 {
   margin-top: 2em;
}

subtitle {
   display:block;
   font-family: "PT Serif", serif;
   font-size: 32px;
   font-style: italic;
   font-weight: 100;
}

p {
  line-height: 150%;
  width: 720px;
}

a {
  color: steelblue;
  cursor: auto;
}

a:not(:hover) {
   text-decoration: none;
}

pre {
   border-left: solid 2px #ccc;
   padding-left: 18px;
   margin: 2em 0 2em -20px;
}

aside {
   font-size: small;
   right: 0;
   position: absolute;
   width: 180px;
}

#nav {
        left: 5px;
        font-family: "Lato", serif;
        font-weight: 700;
        list-style: none;
        margin: 0;
        position: fixed;
        top: 10px;
        box-sizing: border-box;
}


#nav li {
        margin-bottom: 0px;
}

#nav a {
        color: #333;
        display: block;
        font-size: 14px;
        border-left: 3px solid #fcfcfa;
        padding: 5px 10px;
        text-decoration: none;
}

#nav a:hover {
   border-left: 3px solid steelblue;
}

#nav .current a {
   border-left: 3px solid steelblue;
}

.axis path,
.axis line {
        fill: none;
        shape-rendering: crispEdges;
}

.axis text {
        font-family: sans-serif;
        font-size: 11px;
}

.line {
 fill: none;
 stroke: steelblue;
 stroke-width: 1.5px;
}

.graph-svg-component {
    background-color: AliceBlue;
}

.slider-width
{
    width: 500px;
}

.arc path {
  stroke: #fff;
}

.area {
  fill: #e7e7e7;
}

</style>
<body>
  <ul id="nav">
    <li class="current"><a href="#intro">Intro</a></li>
    <li><a href="#problem">Problem</a></li>
    <li><a href="#model">Model</a></li>
    <li><a href="#datamatrix">Risk and Return</a></li>
    <li><a href="#implementation">Implementation</a></li>
    <li><a href="#demo">Live Demo</a></li>
  </ul>
  <div id="container">
    <div class="section" id="intro">
      <h1>Markowitz Portfolio Optimization</h1>
        <subtitle>with quadratic programming and Gurobi</subtitle>
    </div>

    <p> In this example we'll solve a Portfolio Optimization problem: for a set of stocks held
    over a period of time, how do we maximize the expected return while minimizing
      the risk? </p>

    <p> We'll construct a mathematical model of the business problem, implement this model in
    Gurobi's Python interface, and compute and visualize an optimal solution.</p>

    <div class="section" id="problem">
      <h2><a href="#problem" name="problem">Problem Description</a></h2>

      <p>
      We consider the classical portfolio problem introduced by Harry Markowitz in 1952.
      The basic concept behind this theory is that assets in a portfolio should not be chosen
      based on individual merit, but rather as a whole taking into consideration the correlations
      between assets.
      </p>

      <p>
      The model is based on a tradeoff between risk and expected return. Indeed, to maximize
      return, one could just invest all the wealth in the stock with the largest return.
      However, this is clearly a risky strategy, so it is often better to distribute the wealth
      over different assets to reduce the risk.
      </p>

      <p>
      We will apply our model to real stocks using data from the Yahoo Finance API. Using the Live Demo,
      you can create a portfolio and add any stock while deciding how much risk you allow. Gurobi will
      then compute the portfolio distribution which maximizes your return.
      </p>
    </div>
    <div class="section" id="model">
      <h2><a href="#model" name="model">Mathematical Model</a></h2>

      <p>
      We consider $n$ stocks held over a period of time (Add reference to Boyd). We denote by $x_i$ the fraction
      of the total wealth invested in stock $i$, i.e. $\sum_{i=1}^{n} x_i = 1$. In this way, a long position corresponds
      to $x_i > 0$ and a short position to $x_i < 0$. If we assume we cannot go short by a larger amount than $s_i$, we have the constraint
      \[
        x_i \geq s_i
      \]
      for each stock $i$.
      </p>

      <p>
      We denote by $r_i$ expected return of stock $i$ over the time period. The total return of the portfolio is then given by
      \[
        \text{return} = r^T x
      \]
      Since we have normalised the $x$ variables, this corresponds to a fractional return. For example, if $\text{return} = 1.12$
      this corresponds to 12% increase in the total value of the portfolio.
      </p>

      <p> To estimate the risk we use the variance, which is defined as
      \[
        \text{variance} = x^T \Sigma x
      \]
      where $\Sigma$ is the covariance matrix of the return. We wish to bound the risk, so we can introduce a parameter $\sigma_{max}$
      which will correspond to the maximum standard deviation (risk) allowed. This imposes a constraint
      \[
        x^T \Sigma x \leq \sigma_{max}^2
      \]
      </p>

      <p> So finally our model becomes
       \[
      \begin{array}{ll}
      \text{maximize} & r^T x \\
      \text{subject to} & \sum_{i=1}^{n} x_i = 1 \\
                        & x_i \geq 0 \quad \text{for} \, i=1,..,n \\
                        & x^T \Sigma x \leq \sigma_{max}^2
      \end{array}
      \]
      Note that the constraint $x_i \geq 0$ means we do not go short.
      </p>

      </div>
      <div class="section" id="datamatrix">
      <h2><a href="#datamatrix" name="datamatrix">Risk and Return</a></h2>
      <p>
      There are several ways of computing the expected return and the variance. For this implementation, we use data collected from Yahoo Finance API
      giving the closing price of various stocks for the past $N+1$ days. We can then use this data to estimate the return and variance.
      </p>

      <p>
      For $n$ stocks and $N+1$ daily closing prices we define an $N \times n$ data matrix $D$, so that each
      column holds all the information for a single stock. So for each stock $j$ we define
       \[
      D_{ij} = \frac{ \text{closing price of $jth$ stock on $(i+1)th$ day}}{ \text{closing price of $jth$ stock on $ith$ day}}
      \]</p>

      <p> We can then estimate the expected return $r$ for each stock simply as the mean over the time period
      \[ r = \frac{1}{N} D^T \mathbf{1}
      \]
      so that the $ith$ entry of this vector corresponds to the expected return for stock $i$ ($\mathbf{1}$ denotes the vector of ones).</p>

      <p> We use the unbiased estimator for the covariance matrix
      \[
      \Sigma = \frac{1}{N-1}(D - \mathbf{1}r^T ) ^T (D - \mathbf{1}r^T )
      \]</p>
    </div>

    <div class="section" id="implementation">
      <h2><a href="#implementation" name="implementation">Implementation</a></h2>
      <p>Below is the full implementation of the model (and the associated data) in
        Gurobi's Python interface:
      </p>
      <pre>
        from gurobipy import *

        m = Model()

        n = len(r) # number of stocks

        # Add variables (one for each stock)
        x = {};
        for i in range(n):
            x[i] = m.addVar(lb=0, vtype=GRB.CONTINUOUS, name = 'x' + str(i))

        m.update()

        # Add constraints
        m.addConstr(quicksum(x[i] for i in range(n)) == 1)

        variance = 0
        for i in range(n):
            for j in range(n):
                variance += x[i]*Sigma[i][j]*x[j]

        # Set objective
        m.setObjective(quicksum(r[i]*x[i] for i in range(n)), GRB.MAXIMIZE)

        m.addConstr(variance <= maxRisk*maxRisk)

        m.update()

        m.optimize()
      </pre>
    </div>
    <div class="section" id="demo">
      <h2><a href="#demo" name="demo">Live Demo</a></h2>
      <p> Best investments based on last 50 days of trading.</p>
      <input id="stock_symbol" type="text" value="BA">
      <button class="pure-button" onclick="add_quote()">Add Stock</button>
      <p></p>
      <!-- Slider -->
      <label for=myRange>Risk</label>
      <input type="range" min = 0.005 max = 0.03 step = 0.0001 id="myRange" value="0.01" oninput="outputUpdate(value)" class="slider-width">
      <output for=myRange id=riskDisplay>0.01</output>
      <script>
      function outputUpdate(value) {
        document.querySelector('#riskDisplay').value = value;
      }
      </script>

      <div id="demoarea">
      </div>
      <button class="pure-button" onclick="compute()">Compute Optimal Portfolio</button>
    </div>

    <div style="min-height:100px"></div>
<!--[if gt IE 8]><!--><script src="//ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script><!--<![endif]-->
<script src="http://davist11.github.io/jQuery-One-Page-Nav/jquery.nav.js"></script>
<script>
  $(document).ready(function() {
  console.log('calling onePageNav');
  $('#nav').onePageNav();
  });
</script>

<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script>

// Binary variable to see if stock was just added (1) or not (0)
var addStock = 0;

//Width and height
var width = 800;
var height = 500;
var padding = 50;

var time_height = 70;

var formatAsPercentage = d3.format(".1%")
var formatAsPercentage3 = d3.format(".3%")

d3.select("#demoarea")
      .append("div")
      .attr("id", "timeseries");

var svg = d3.select("#demoarea")
              .append("svg")
              .attr("width", width)
              .attr("height", height);


var donutG = svg.append("g")
              .attr("transform", "translate(" + width/2 + "," + height/2 + ")");
var labelG = svg.append("g");
var titleG = svg.append("g");

var maxRisk = 0.002; // This can be varied with slider
var r = [];
var Sigma = [];

// These variables needed for stock functions
var stock_data = {};
var parseDate = d3.time.format("%Y-%m-%d").parse;
var quote;
var symbolList = [];


var x = d3.time.scale()
         .range([0, width])

var y = d3.scale.linear()
          .range([time_height, 0])

var area = d3.svg.area()
             .x(function (d) { return x(d.date); })
             .y0(time_height)
             .y1(function (d) { return y(d.close); });

var line = d3.svg.area()
              .x(function (d) { return x(d.date); })
              .y(function (d) { return y(d.close); })

var timeseries_data = [];


// Start with a few stocks
get_quote("GM", 100);   // General Motors
get_quote("GOOG", 100); // Google
get_quote("YHOO", 100); // Yahoo
get_quote("TM", 100);   // Toyota
get_quote("NESN", 100); // Nestle
get_quote("SNE", 100);  // Sony

function compute() {
  console.log("in compute")
  var numDays = 50; // Take only the first days for testing
  var stock_symbols = symbolList;
  var numStocks = stock_symbols.length;
  console.log(stock_symbols) // list of different stocks (e.g. ["BA", "GM"])

  var rawData = [];

  for (var i = 0; i < numStocks; i++) {
    stock_i = stock_data[stock_symbols[i]]; // This contains all data for stock i
    rawData.push(stock_i.slice(0,numDays + 1));
  }

  var D = [];

  // (Raw data)_ji contains closing price of jth stock on ith day
  for (var i = 0; i < numDays; i++) {
    day_i_prices = [];
    for (var j = 0; j < numStocks; j++) {
      day_i_prices.push(rawData[j][i+1] / rawData[j][i])
    }
    D.push(day_i_prices)
  }

  console.log('D', D);

  // Compute return (r) and covariance (Sigma)
  r = []; var average;
  for (var i = 0; i < numStocks; i++) {
    average = 0;
      for (var j = 0; j < numDays; j++) {
        average += D[j][i];
      }
    r.push(average/numDays);
  }

  console.log('r', r);

  Sigma = []; var row; var entry;
  for (var i = 0; i < numStocks; i++) {
    row = [];
    for (var j = 0; j < numStocks; j++) {
      term = 0;
      for (var k = 0; k < numDays; k++) {
        term += (D[k][i] - r[i])*(D[k][j] - r[j]);
      }
      row.push(term/(numDays-1));
    }
    Sigma.push(row);
  }

  console.log('Sigma', Sigma);


  var slider = document.getElementById("myRange").value;
  maxRisk = parseFloat(slider);

  console.log('maxRisk', maxRisk);

  d3.json('/markowitz')
    .header('Content-Type', 'application/json')
    .post(JSON.stringify({'return': r, 'Sigma': Sigma, 'maxRisk': maxRisk}), serverResponse);
}

var radius = Math.min(width, height) / 2;
var color = d3.scale.ordinal()
    .range(["#98abc5", "#8a89a6", "#7b6888", "#6b486b", "#a05d56", "#d0743c", "#ff8c00"]);

var arc = d3.svg.arc()
    .outerRadius(radius - 10)
    .innerRadius(radius - 120);

var pie = d3.layout.pie()
    .sort(function (a, b) { return d3.ascending(a.percent, b.percent); })
    .value(function(d) { return d.percent; });

function serverResponse(error, data) {
   console.log('serverResponse');
   console.log('data', data);
   if (!error) {
      if ('solution' in data) {
        var solution = data.solution;
        console.log('solution', solution);

        var maxRet = solution['Return'];
        var stocks = solution['Stocks'];

        var piedata = [];
        for (var i=0; i < stocks.length; i++) {
            piedata.push({ percent: stocks[i], symbol: symbolList[i] });
        }
        console.log(piedata);

        color.domain(symbolList);

        console.log("color YHOO", color("YHOO"));

        var maxStock = d3.max(stocks);

        if (maxRet === 0) {
            var title = "Problem infeasible. Try increasing risk";
        } else {
           var title = "Profit: " + formatAsPercentage3(maxRet - 1);
        }

        titleG.selectAll("text").remove();

        titleG.append("text")
           .text(title)
           .attr("x", width/2)
           .attr("y", height/2)
           .attr("font-family", "sans-serif")
           .attr("font-size", "16px")
           .attr("fill", "black")
           .attr("text-anchor", "middle");

        donutG.selectAll(".arc").remove();

        var g = donutG.selectAll(".arc")
                   .data(pie(piedata))
                 .enter().append("g")
                    .attr("class", "arc");

        g.append("path")
         .attr("d", arc)
         .style("fill", function (d) {
                          return color(d.data.symbol);
                          });

        g.append("text")
          .attr("transform", function (d) { return "translate(" + arc.centroid(d) + ")"; })
          .attr("dy", ".3em")
          .style("text-anchor", "middle")
          .text(function (d) {
                          if (d.data.percent > 0.01) {
                            return d.data.symbol + " " + formatAsPercentage(d.data.percent);
                          } else {
                             return "";
                          }
                          });

      }
   }
}

// Function for user to add quote
function add_quote() {
  var symbol =  $('#stock_symbol').val();
  if (symbol.length == 0) return;
  get_quote(symbol, 100);
}



function get_quote(symbol, numdays) {
 // goes numdays back. Note that there will be less than numdays
 // quotes returned, since the stock market is closed on weekends

 if (symbolList.indexOf(symbol) !== -1) {
    alert(symbol + " has already been added!");
    return;
 }

 callbackname = "quote" + symbol;

 var dateFormat = d3.time.format('%Y-%m-%d')
 enddate = dateFormat(new Date());
 startdate = dateFormat(d3.time.day.offset(new Date(), -numdays))

 $.ajax({
        url: "https://query.yahooapis.com/v1/public/yql?q=select%20*%20from%20yahoo.finance.historicaldata%20where%20symbol%20%3D%20%22" + symbol + "%22%20and%20startDate%20%3D%20%22" + startdate + "%22%20and%20endDate%20%3D%20%22" + enddate + "%22&format=json&diagnostics=true&env=store%3A%2F%2Fdatatables.org%2Falltableswithkeys&callback=" + callbackname,
        dataType: "jsonp",
        jsonp: "callback",
        jsonpCallback: callbackname
    });

 window[callbackname] = function(data) {
        try {
          var stock_quotes = data.query.results.quote;
        }
        catch(err) {
          alert("Failed to load data. Check if stock name is correct");
          return;
        }
        var cur;
        var my_data = [];
        var symbol = stock_quotes[0].Symbol;
        var price_data = [];
        var max_price = 0;
        var min_price = Infinity;
        for (var i=0; i < stock_quotes.length; i++) {
           cur = stock_quotes[i];
           my_data[i] = { date: parseDate(cur.Date), close: +cur.Close}
           price_data[i] = +cur.Close;
           max_price = Math.max(max_price, +cur.Close);
           min_price = Math.min(min_price, +cur.Close);
        }

        stock_data[symbol] = price_data;
        console.log('Got ', my_data.length, 'closing prices');
        symbolList.push(symbol); // Add the symbol of the stock just added

        timeseries_data.push({    symbol: symbol,
                                    data: my_data,
                               max_price: max_price,
                               min_price: min_price });

        addStock = 1; // added stock

        x.domain([ my_data[0].date, my_data[my_data.length-1].date ]);

        d3.select("#timeseries").selectAll("svg").remove();

        var timeseries = d3.select("#timeseries").selectAll("svg")
                         .data(timeseries_data)
                         .enter().append("svg")
                           .attr("width", width + 20)
                           .attr("height", time_height + 40)
                         .append("g")
                           .attr("transform", "translate(10, 10)");

        timeseries.append("path")
               .attr("class", "area")
               .attr("d", function (d) {
                                         y.domain([d.min_price, d.max_price]);
                                         return area(d.data);
                                       });

        timeseries.append("path")
              .attr("class", "line")
              .attr("d", function (d) {
                                       y.domain([d.min_price, d.max_price]);
                                       return line(d.data);
                                      });
        timeseries.append("text")
                  .attr("x", width - 6)
                  .attr("y", time_height - 6)
                  .style("text-anchor", "end")
                  .text(function (d) { return d.symbol; });

    };
    return;
}

</script>
